МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Звіт з виконання
Лабораторної роботи №1
на тему:
ВНУТРІШНІ ФОРМИ ПОДАНННЯ ВХІДНОЇ ПРОГРАМИ
з курсу:
«Лінгвістичне забезпечення САПР»
1. МЕТА РОБОТИ
Закріпити навики одержання бездужкового польського запису, використовуючи метод Дейкстри і бінарні дерева.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Для оптимізації процесу компіляції первісна текстова програма перекладається у деяку внутрішню форму, зручнішу для подальшої машинної обробки. Проміжна програма виробляється синтаксичним аналізатором і відображає структуру первинної програми. У той самий час оператори проміжної програми розміщуються в тому випадку, в якому вони повинні виконуватись.
Найрозповсюдженішими формами подання вхідної програми є:
1) Бездужковий запис (польський запис);
2) Тетради;
3) Тріади;
4) Зв’язані спискові структури;
5) Зображаючі дерева.
ЗАПИС БЕЗДУЖКОВИЙ. АЛГОРИТМ ДЕЙКСТРИ.
Запис бездужковий – подання виразу, при якому порядок виконання операцій визначається її контекстом і позицією у формулі.
Існують два види бездужкових записів: прямий, або префікс ний і інверсний, або постфікс ний.
Для автоматизованих обчислень найзручніше використовувати постфікс ний запис бездужковий.
Відомо декілька методів отримання пост фіксовано польського запису. Найефективніший є алгоритм Дейкстри.
Цей метод базується на використанні стека для збереження знаків операцій.
Кожному обмежувачу, який входить у вираз, присвоюється пріоритет.
Для знаків операцій пріоритет зростає в порядку, зворотному до старшинства операцій. Алгоритмічні і логічні вирази розглядаються як вхідна стрічка символів зліва направо.
Операнди переписуються у вихідну стрічку, а знаки операцій поміщають у стек операцій.
Якщо пріоритет вхідного знака операцій дорівнює нулю або більший від пріоритету знака, який є на вершині стека, то новий знак додається до вершини стека. В протилежному випадку із стека «виштовхується» і переписується у вихідні стрічці знак, що розташований у вершині, а також наступні за ним знаки з пріоритетом більшим або таким, що дорівнює пріоритету вхідного знака. Після цього вхідний знак додається до вершини стека.
Обмежувачі
Пріоритет
( [ if
0
= ) then else
1
2
3
^
4
]
5
> ≥ = ≤ ≠ <
6
+ -
7
* / ÷ @
8
?
9
Деякі особливості має й робота з дужкам. Відкриваючі дужки мають нульовий пріоритет, просто записуються у вершину стеку і не виштовхують жодного знака. Виштовхувати відкриваючу дужку може тільки закриваюча. Закриваюча дужка має пріоритет один, який не перевищує пріоритету будь-якої операції. Поява закриваючої дужки викликає виштовхування усіх знаків операцій до найближчої дужки. В стек закриваюча дужка не записується і у вихідну стрічку не переноситься. Відкриваюча і закриваюча дужки взаємно знищується.
ФОРМУВАННЯ БЕЗДУЖКОВОГО ЗАПИСУ ЗА ДОПОМОГОЮ БІНАРНОГО ДЕРЕВА.
Арифметичний вираз можна подати у вигляді дерева. Вузли дерева відповідають операціям, а гілки – операндам. Ліва гілка, яка виходить з вузла, відповідає лівому операнду., права – правому. Операціям, які виконуються раніше, відповідають нижче розміщені вузли. Верхній вузол – корінь дерева відповідає операція, яка виконується останньою.
На рис. 2. показано дерево виразу: .
Рис. 2. Обхід дерева для одержання постфіксного польського запису .
Якщо, почавши з нижнього листка крайньої лівої гілки дерева, обійти усі листки і вузли дерева, так щоб гілки розглядались зліва направо, а вузол розглядався після обходу усіх гілок, що з нього виходять, то послідовність перегляду вузлів і листків дасть постфіксний польський запис.
На рис. 3. показано дерево виразу і порядок обходу для одержання префіксного польського запису.
Рис. 3. Обхід бінарного дерева для одержання префіксного польського запису .
Якщо, почавши з верхнього вузла, обійти усі вузли і листки дерева, так щоб верхній вузол розглядався раніше ніж нижній, і одразу після розгляду вузла проглядалися зліва направо гілки, як...
